package com.company.algo.niuke;

import com.company.algo.debugUtils.DebugUtils;
import com.company.algo.pojo.ListNode;

/**【做过又忘了】
 * 给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
 * 要求时间复杂度O(n)---只能一次遍历
 *我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，
 * 那么删除掉 p 的下一个指针就完成了要求。
 * 1.设置虚拟节点 dummyHead 指向 head
 * 2.设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
 * 3.移动 q，直到 p 与 q 之间相隔的元素个数为 n
 * 4.同时移动 p 与 q，直到 q 指向的为 NULL
 * 5.将 p 的下一个节点指向下下个节点
 */
public class DeleteLastNthNode {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode p=dummyHead,q=dummyHead;
        for (int i = 0; i < n+1; i++) {
            if (q == null) return null;
            q = q.next;
        }
        while (q!=null){
            p = p.next;
            q = q.next;
        }
        ListNode deleted = p.next;
        p.next = deleted.next;
        return dummyHead.next;
    }

    public static void main(String[] args) {
        DeleteLastNthNode Main = new DeleteLastNthNode();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        DebugUtils.printListNode(Main.removeNthFromEnd(head,2));
    }
}
